<!DOCTYPE html>
<html>
  <head>
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
  <meta content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0" name="viewport">
  <meta name="description" content="tong.li&#39;s blog">
  <meta name="keyword" content="彤哥哥博客，95后技术爱好者,现就职于同程旅行/同程艺龙上海分公司，专注于互联网技术分享的平台。">
  
    <link rel="shortcut icon" href="/css/images/icon.png">
  
  <title>
    
      数据结构之排序 | 彤哥哥的博客
    
  </title>
  <link href="https://cdn.staticfile.org/font-awesome/4.7.0/css/font-awesome.min.css" rel="stylesheet">
  <link href="https://cdn.staticfile.org/nprogress/0.2.0/nprogress.min.css" rel="stylesheet">
  <link href="https://cdn.staticfile.org/highlight.js/9.12.0/styles/tomorrow-night.min.css" rel="stylesheet">
  
<link rel="stylesheet" href="/css/style.css">

  
  <script src="https://cdn.staticfile.org/jquery/3.2.1/jquery.min.js"></script>
  <script src="https://cdn.staticfile.org/geopattern/1.2.3/js/geopattern.min.js"></script>
  <script src="https://cdn.staticfile.org/nprogress/0.2.0/nprogress.min.js"></script>
  
    
<script src="/js/qrious.js"></script>

  
  
  
  
    <!-- MathJax support START -->
    <script type="text/x-mathjax-config">
      MathJax.Hub.Config({
        tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
        }
      });
    </script>

    <script type="text/x-mathjax-config">
      MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
      });
    </script>
    <script type="text/javascript" src="https://cdn.staticfile.org/mathjax/2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
    <!-- MathJax support END -->
  


  
  
    
<script src="/js/local-search.js"></script>


<meta name="generator" content="Hexo 5.4.2"></head>
<div class="wechat-share">
  <img src="/css/images/logo.png" />
</div>
  <body>
    <header class="header fixed-header">
  <div class="header-container">
    <a class="home-link" href="/">
      <div class="logo"></div>
      <span>彤哥哥的博客</span>
    </a>
    <ul class="right-list">
      
        <li class="list-item">
          
            <a href="/" class="item-link">主页</a>
          
        </li>
      
        <li class="list-item">
          
            <a href="/series/" class="item-link">分类</a>
          
        </li>
      
        <li class="list-item">
          
            <a href="/tags/" class="item-link">标签</a>
          
        </li>
      
        <li class="list-item">
          
            <a href="/archives/" class="item-link">归档</a>
          
        </li>
      
        <li class="list-item">
          
            <a href="/project/" class="item-link">项目</a>
          
        </li>
      
        <li class="list-item">
          
            <a href="/about/" class="item-link">关于</a>
          
        </li>
      
      
        <li class="menu-item menu-item-search right-list">
    <a role="button" class="popup-trigger">
        <i class="fa fa-search fa-fw"></i>
    </a>
</li>
      
    </ul>
    <div class="menu">
      <span class="icon-bar"></span>
      <span class="icon-bar"></span>
      <span class="icon-bar"></span>
    </div>
    <div class="menu-mask">
      <ul class="menu-list">
        
          <li class="menu-item">
            
              <a href="/" class="menu-link">主页</a>
            
          </li>
        
          <li class="menu-item">
            
              <a href="/series/" class="menu-link">分类</a>
            
          </li>
        
          <li class="menu-item">
            
              <a href="/tags/" class="menu-link">标签</a>
            
          </li>
        
          <li class="menu-item">
            
              <a href="/archives/" class="menu-link">归档</a>
            
          </li>
        
          <li class="menu-item">
            
              <a href="/project/" class="menu-link">项目</a>
            
          </li>
        
          <li class="menu-item">
            
              <a href="/about/" class="menu-link">关于</a>
            
          </li>
        
      </ul>
    </div>
    
      <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
            <span class="search-icon">
                <i class="fa fa-search"></i>
            </span>
            <div class="search-input-container">
                <input autocomplete="off" autocapitalize="off"
                    placeholder="Please enter your keyword(s) to search." spellcheck="false"
                    type="search" class="search-input">
            </div>
            <span class="popup-btn-close">
                <i class="fa fa-times-circle"></i>
            </span>
        </div>
        <div id="search-result">
            <div id="no-result">
                <i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>
            </div>
        </div>
    </div>
</div>
    
  </div>
</header>

    <div id="article-banner">
  <h2>数据结构之排序</h2>
  <p class="post-date">2018-05-10</p>
  <div class="arrow-down">
    <a href="javascript:;"></a>
  </div>
</div>
<main class="app-body flex-box">
  <!-- Article START -->
  <article class="post-article">
    <section class="markdown-content"><p>数据结构和算法是整个计算机科学与技术领域永远逃避不了的话题,博主大学有过数据结构这门学科,不过特别后悔当时没有好好学习.仅学的那么点东西现在几乎忘得一干二净.虽说学的浅薄,但对整个编程思想还是很有帮助的.</p>
<h2 id="十种常见排序算法"><a href="#十种常见排序算法" class="headerlink" title="十种常见排序算法"></a>十种常见排序算法</h2><p>十种常见排序算法可分为两大类:</p>
<ul>
<li>非线性时间比较类排序：通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此称为非线性时间比较类排序.</li>
<li>线性时间非比较类排序：不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此称为线性时间非比较类排序.</li>
</ul>
<p><img src="https://ltyeamin.github.io/imgs/2020/07/20200731174824.png" alt="十大排序算法分类"><br><img src="https://ltyeamin.github.io/imgs/2020/07/20200731174842.png" alt="十大排序算法复杂度"></p>
<h2 id="冒泡排序"><a href="#冒泡排序" class="headerlink" title="冒泡排序"></a>冒泡排序</h2><p>冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法.它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名“冒泡排序”.</p>
<h3 id="算法描述"><a href="#算法描述" class="headerlink" title="算法描述"></a>算法描述</h3><ul>
<li>比较相邻的元素。如果第一个比第二个大,就交换它们两个;</li>
<li>对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;</li>
<li>针对所有的元素重复以上的步骤,除了最后一个;<h3 id="动图演示"><a href="#动图演示" class="headerlink" title="动图演示"></a>动图演示</h3><img src="https://ltyeamin.github.io/imgs/2020/07/20200731174847.gif" alt="冒泡排序"><h3 id="代码演示"><a href="#代码演示" class="headerlink" title="代码演示"></a>代码演示</h3><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line">/**</span><br><span class="line">  * </span><br><span class="line">  * 冒泡排序</span><br><span class="line">  *</span><br><span class="line">  * @author tong.li</span><br><span class="line">  * @param arr = &#123;6,3,8,2,9,1&#125;</span><br><span class="line">  * </span><br><span class="line">  * 第0趟比较5次: 3,6,8,2,9,1 =&gt; 3,6,8,2,9,1 =&gt; 3,6,2,8,9,1 =&gt; 3,6,2,8,9,1 =&gt; 3,6,2,8,1,9</span><br><span class="line">  * 第1趟比较4次: 3,6,2,8,1,9 =&gt; 3,2,6,8,1,9 =&gt; 3,2,6,8,1,9 =&gt; 3,2,6,1,8,9 </span><br><span class="line">  * 第2趟比较3次: 2,3,6,1,8,9 =&gt; 2,3,6,1,8,9 =&gt; 2,3,1,6,8,9</span><br><span class="line">  * 第3趟比较2次: 2,3,1,6,8,9 =&gt; 2,1,3,6,8,9 </span><br><span class="line">  * 第4趟比较1次: 1,2,3,6,8,9 </span><br><span class="line">  */</span><br><span class="line">public static void bubbleSort(int ... arr) &#123;</span><br><span class="line">  if ( arr==null || arr.length &lt;= 0) &#123;</span><br><span class="line">			return;</span><br><span class="line">	&#125;</span><br><span class="line">  // 外循环控制趟数</span><br><span class="line">  for (int i = 0; i &lt; arr.length; i++) &#123;</span><br><span class="line">    // 内循环控制次数</span><br><span class="line">    // for(int j=1;j&lt;arr.length-i;j++)&#123;</span><br><span class="line">    for (int j = 0; j &lt; arr.length - 1 - i; j++) &#123;</span><br><span class="line">      //相邻两个元素进行比较</span><br><span class="line">      if( arr[j] &gt; arr[j + 1]) &#123;</span><br><span class="line">        // 采用异或方式进行变量互换</span><br><span class="line">        arr[j] = arr[j] ^ arr[j + 1];</span><br><span class="line">        arr[j + 1] = arr[j] ^ arr[j + 1];</span><br><span class="line">        arr[j] = arr[j] ^ arr[j + 1];</span><br><span class="line">      &#125;</span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="快速排序-面试官最爱问的排序算法"><a href="#快速排序-面试官最爱问的排序算法" class="headerlink" title="快速排序(面试官最爱问的排序算法)"></a>快速排序(面试官最爱问的排序算法)</h2>快速排序(Quicksort)是对冒泡排序的一种改进.<br>快速排序由C.A.R.Hoare在1962年提出.基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列.最坏情况的时间复杂度为O(n^2).最好情况时间复杂度为O(nlog2n).<h3 id="算法描述-1"><a href="#算法描述-1" class="headerlink" title="算法描述"></a>算法描述</h3>快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下:</li>
<li>从数列中挑出一个元素.称为”基准”（pivot）;</li>
<li>重新排序数列.所有元素比基准值小的摆放在基准前面.所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后.该基准就处于数列的中间位置。这个称为分区（partition）操作;</li>
<li>递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。<h3 id="动图演示-1"><a href="#动图演示-1" class="headerlink" title="动图演示"></a>动图演示</h3><img src="https://ltyeamin.github.io/imgs/2020/07/20200731174903.gif" alt="快速排序"><br><img src="https://ltyeamin.github.io/imgs/2020/07/20200731174912.jpeg" alt="快速排序图例"></li>
</ul>
<h3 id="代码演示-1"><a href="#代码演示-1" class="headerlink" title="代码演示"></a>代码演示</h3><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br></pre></td><td class="code"><pre><span class="line">/**</span><br><span class="line">  * </span><br><span class="line">  * 快速排序</span><br><span class="line">  * </span><br><span class="line">  * @param arr = &#123;6,3,8,2,9,1&#125;</span><br><span class="line">  * @author tong.li</span><br><span class="line">  * </span><br><span class="line">  * 分析: </span><br><span class="line">  * 	a. 一般以首元素或尾元素为基准,这里以首元素6为基准,有比基准数大的数放在6的右边,比基准数小的数放在6的左边,我们的目标是将6挪到序列中间的某个位置.</span><br><span class="line">  * 	b. 假设这个位置是k,现在需要寻找这个k的位置.分别从数组的两端开始探测,先从右往左找一个小于6的数(总是如此),再从左到右找一个大于6的数,两端停下来后交换它们.</span><br><span class="line">  * 	c. 这里可以用两个变量i和j,分布指向数组最左边和最右边.这两个变量有个好听的名字:哨兵i和哨兵j,哨兵i初始指向索引为0的6,哨兵j初始指向索引为5的1</span><br><span class="line">  * 步骤:</span><br><span class="line">  * 	1. 先让哨兵j动起来向左(j--)找小于6的值,第一次找到为1停下来.</span><br><span class="line">  *  2. 紧接着哨兵i向右移动(i++)找大于6的值,第一次找到为8停下来.</span><br><span class="line">  *  3. 进行交换停下来的值,即1和8进行交换.交换后的数组为:6,3,1,2,9,8</span><br><span class="line">  *  4. 在3交换后的基础上继续1,2步骤,哨兵j一直往左移遇到2,哨兵i一直往右移遇到9,两个哨兵在2已经相遇了,我们应该将基准6与和2进行交换,即交换后的数组为:2,3,1,6,9,8,此时第一轮探测真正结束</span><br><span class="line">  *  此时旧基准数6已经归位,新基准数为2,以6位分界点把数组拆成了两个小数组,左数组为小于6的,右边数组都是大于6的,目前两个数组的顺序都是混乱的,不过不要紧,继续按1,2,3步骤分别对两个数组耐心处理</span><br><span class="line">  *  5. 先处理6左边的小数组2,3,1,以2为基准数,找到1和3,交换后2,1,3,继续找在1相遇,交换后为1,2,3</span><br><span class="line">  *  6. 再来处理6右边的小数组9,8,以9为基准数,两者在8相遇,交换后为8,9</span><br><span class="line">  *  7. 到此完全结束,排序后为1,2,3,6,8,9.快速排序的每一轮处理其实就是将这一轮的基准数归位,直到所有的数都归位为止,排序就结束了.</span><br><span class="line">  *  </span><br><span class="line">  */</span><br><span class="line">public static void quickSort(int[] arr, int low, int high) &#123;</span><br><span class="line">  int i, j, temp, t;</span><br><span class="line">  if (low &gt; high) &#123;</span><br><span class="line">    return;</span><br><span class="line">  &#125;</span><br><span class="line">  i = low;</span><br><span class="line">  j = high;</span><br><span class="line">  // temp就是基准位</span><br><span class="line">  temp = arr[low];</span><br><span class="line"></span><br><span class="line">  while (i &lt; j) &#123;</span><br><span class="line">    // 先看右边.依次往左递减</span><br><span class="line">    while (temp &lt;= arr[j] &amp;&amp; i &lt; j) &#123;</span><br><span class="line">      j--;</span><br><span class="line">    &#125;</span><br><span class="line">    // 再看左边.依次往右递增</span><br><span class="line">    while (temp &gt;= arr[i] &amp;&amp; i &lt; j) &#123;</span><br><span class="line">      i++;</span><br><span class="line">    &#125;</span><br><span class="line">    // 如果满足条件则交换</span><br><span class="line">    if (i &lt; j) &#123;</span><br><span class="line">      t = arr[j];</span><br><span class="line">      arr[j] = arr[i];</span><br><span class="line">      arr[i] = t;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">  &#125;</span><br><span class="line">  // 最后将基准为与i和j相等位置的数字交换</span><br><span class="line">  arr[low] = arr[i];</span><br><span class="line">  arr[i] = temp;</span><br><span class="line">  // 递归调用左半数组</span><br><span class="line">  quickSort(arr, low, j - 1);</span><br><span class="line">  // 递归调用右半数组</span><br><span class="line">  quickSort(arr, j + 1, high);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<h2 id="选择排序"><a href="#选择排序" class="headerlink" title="选择排序"></a>选择排序</h2><p>选择排序(Selection sort)是一种简单直观的排序算法.它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完.</p>
<h3 id="算法描述-2"><a href="#算法描述-2" class="headerlink" title="算法描述"></a>算法描述</h3><p>n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下:</p>
<ul>
<li>初始状态：无序区为R[1..n],有序区为空;</li>
<li>第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;</li>
<li>n-1趟结束,数组有序化了;<h3 id="动图演示-2"><a href="#动图演示-2" class="headerlink" title="动图演示"></a>动图演示</h3><img src="https://ltyeamin.github.io/imgs/2020/07/20200731174918.gif" alt="选择排序"><h3 id="代码演示-2"><a href="#代码演示-2" class="headerlink" title="代码演示"></a>代码演示</h3><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line">/**</span><br><span class="line">  * </span><br><span class="line">  * 选择排序</span><br><span class="line">  *</span><br><span class="line">  * @author tong.li</span><br><span class="line">  * @param arr = &#123;6,3,8,2,9,1&#125;</span><br><span class="line">  * </span><br><span class="line">  *第0趟比较5次: 3,6,8,2,9,1 =&gt; 3,6,8,2,9,1 =&gt; 2,6,8,3,9,1 =&gt; 2,6,8,3,9,1 =&gt; 1,6,8,3,9,2</span><br><span class="line">  *第1趟比较4次: 1,6,8,3,9,2 =&gt; 1,3,8,6,9,2 =&gt; 1,3,8,6,9,2 =&gt; 1,2,8,6,9,3</span><br><span class="line">  *第2趟比较3次: 1,2,6,8,9,3 =&gt; 1,2,6,8,9,3 =&gt; 1,2,3,8,9,6</span><br><span class="line">  *第3趟比较2次: 1,2,3,8,9,6 =&gt; 1,2,3,6,9,8</span><br><span class="line">  *第4趟比较1次: 1,2,3,6,8,9</span><br><span class="line">  */</span><br><span class="line">public static void selectionSort(int... arr) &#123;</span><br><span class="line">  if ( arr==null || arr.length &lt;= 0) &#123;</span><br><span class="line">			return;</span><br><span class="line">	&#125;</span><br><span class="line">  // 外循环控制趟数</span><br><span class="line">  for (int i = 0; i &lt; arr.length - 1; i++) &#123;</span><br><span class="line">    // 内循环控制次数</span><br><span class="line">    for (int j = i + 1; j &lt; arr.length; j++) &#123;</span><br><span class="line">      // 相邻两个元素进行比较</span><br><span class="line">      if (arr[i] &gt; arr[j]) &#123;</span><br><span class="line">        // 采用异或方式进行变量互换</span><br><span class="line">        arr[i] = arr[i] ^ arr[j];</span><br><span class="line">        arr[j] = arr[i] ^ arr[j];</span><br><span class="line">        arr[i] = arr[i] ^ arr[j];</span><br><span class="line">      &#125;</span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
其他排序算法后续更新,请读者持续关注.<h2 id="参考文献"><a href="#参考文献" class="headerlink" title="参考文献:"></a>参考文献:</h2><a target="_blank" rel="noopener" href="http://www.cnblogs.com/onepixel/articles/7674659.html">十大经典排序算法-动图演示</a></li>
</ul>
<p><a target="_blank" rel="noopener" href="http://www.2cto.com/kf/201704/622993.html">堆排序,归并排序,快排-排序王者之争一</a></p>
<p><a target="_blank" rel="noopener" href="http://www.cnblogs.com/Mimick/p/6160468.html">堆排序,归并排序,快排-排序王者之争二</a></p>
</section>
    <!-- Tags START -->
    
      <div class="tags">
        <span>Tags:</span>
        
  <a href="/tags#排序算法" >
    <span class="tag-code">排序算法</span>
  </a>

      </div>
    
    <!-- Tags END -->
    <!-- NAV START -->
    
  <div class="nav-container">
    <!-- reverse left and right to put prev and next in a more logic postition -->
    
      <a class="nav-left" href="/2018/04/04/%E5%86%85%E7%BD%91%E7%A9%BF%E9%80%8F%E7%A5%9E%E5%99%A8-Ngrok/">
        <span class="nav-arrow">← </span>
        
          内网穿透神器-Ngrok
        
      </a>
    
    
      <a class="nav-right" href="/2018/05/15/Spring%E5%AE%B9%E5%99%A8%E4%BB%A5%E5%8F%8ABean%E7%9A%84%E7%94%9F%E5%91%BD%E5%91%A8%E6%9C%9F/">
        
          Spring容器以及Bean的生命周期
        
        <span class="nav-arrow"> →</span>
      </a>
    
  </div>

    <!-- NAV END -->
    <!-- 打赏 START -->
    
      <div class="money-like">
        <div class="reward-btn">
          赏
          <span class="money-code">
            <span class="alipay-code">
              <div class="code-image"></div>
              <b>使用支付宝打赏</b>
            </span>
            <span class="wechat-code">
              <div class="code-image"></div>
              <b>使用微信打赏</b>
            </span>
          </span>
        </div>
        <p class="notice">若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏</p>
      </div>
    
    <!-- 打赏 END -->
    <!-- 二维码 START -->
    
      <div class="qrcode">
        <canvas id="share-qrcode"></canvas>
        <p class="notice">扫描二维码，分享此文章</p>
      </div>
    
    <!-- 二维码 END -->
    
      <!-- Utterances START -->
      <div id="utterances"></div>
      <script src="https://utteranc.es/client.js"
        repo="ltyeamin/blogtalks"
        issue-term="pathname"
        theme="github-light"
        crossorigin="anonymous"
        async></script>    
      <!-- Utterances END -->
    
  </article>
  <!-- Article END -->
  <!-- Catalog START -->
  
    <aside class="catalog-container">
  <div class="toc-main">
    <strong class="toc-title">Catalog</strong>
    
      <ol class="toc-nav"><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#%E5%8D%81%E7%A7%8D%E5%B8%B8%E8%A7%81%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95"><span class="toc-nav-text">十种常见排序算法</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F"><span class="toc-nav-text">冒泡排序</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#%E7%AE%97%E6%B3%95%E6%8F%8F%E8%BF%B0"><span class="toc-nav-text">算法描述</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#%E5%8A%A8%E5%9B%BE%E6%BC%94%E7%A4%BA"><span class="toc-nav-text">动图演示</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#%E4%BB%A3%E7%A0%81%E6%BC%94%E7%A4%BA"><span class="toc-nav-text">代码演示</span></a></li></ol></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F-%E9%9D%A2%E8%AF%95%E5%AE%98%E6%9C%80%E7%88%B1%E9%97%AE%E7%9A%84%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95"><span class="toc-nav-text">快速排序(面试官最爱问的排序算法)</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#%E7%AE%97%E6%B3%95%E6%8F%8F%E8%BF%B0-1"><span class="toc-nav-text">算法描述</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#%E5%8A%A8%E5%9B%BE%E6%BC%94%E7%A4%BA-1"><span class="toc-nav-text">动图演示</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#%E4%BB%A3%E7%A0%81%E6%BC%94%E7%A4%BA-1"><span class="toc-nav-text">代码演示</span></a></li></ol></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F"><span class="toc-nav-text">选择排序</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#%E7%AE%97%E6%B3%95%E6%8F%8F%E8%BF%B0-2"><span class="toc-nav-text">算法描述</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#%E5%8A%A8%E5%9B%BE%E6%BC%94%E7%A4%BA-2"><span class="toc-nav-text">动图演示</span></a></li><li class="toc-nav-item toc-nav-level-3"><a class="toc-nav-link" href="#%E4%BB%A3%E7%A0%81%E6%BC%94%E7%A4%BA-2"><span class="toc-nav-text">代码演示</span></a></li></ol></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#%E5%8F%82%E8%80%83%E6%96%87%E7%8C%AE"><span class="toc-nav-text">参考文献:</span></a></li></ol>
    
  </div>
</aside>
  
  <!-- Catalog END -->
</main>

<script>
  (function () {
    var url = 'http://example.com/2018/05/10/数据结构之排序/';
    var banner = ''
    if (banner !== '' && banner !== 'undefined' && banner !== 'null') {
      $('#article-banner').css({
        'background-image': 'url(' + banner + ')'
      })
    } else {
      $('#article-banner').geopattern(url)
    }
    $('.header').removeClass('fixed-header')

    // error image
    $(".markdown-content img").on('error', function() {
      $(this).attr('src', '/css/images/error_icon.png')
      $(this).css({
        'cursor': 'default'
      })
    })

    // zoom image
    $(".markdown-content img").on('click', function() {
      var src = $(this).attr('src')
      if (src !== '/css/images/error_icon.png') {
        var imageW = $(this).width()
        var imageH = $(this).height()

        var zoom = ($(window).width() * 0.95 / imageW).toFixed(2)
        zoom = zoom < 1 ? 1 : zoom
        zoom = zoom > 2 ? 2 : zoom
        var transY = (($(window).height() - imageH) / 2).toFixed(2)

        $('body').append('<div class="image-view-wrap"><div class="image-view-inner"><img src="'+ src +'" /></div></div>')
        $('.image-view-wrap').addClass('wrap-active')
        $('.image-view-wrap img').css({
          'width': `${imageW}`,
          'transform': `translate3d(0, ${transY}px, 0) scale3d(${zoom}, ${zoom}, 1)`
        })
        $('html').css('overflow', 'hidden')

        $('.image-view-wrap').on('click', function() {
          $(this).remove()
          $('html').attr('style', '')
        })
      }
    })
  })();
</script>


  <script>
    var qr = new QRious({
      element: document.getElementById('share-qrcode'),
      value: document.location.href
    });
  </script>






    <div class="scroll-top">
  <span class="arrow-icon"></span>
</div>
    <footer class="app-footer">
  <p class="copyright">
    &copy; 2024 | Proudly powered by <a href="https://hexo.io" target="_blank">Hexo</a>
    <br>
    Theme by <a target="_blank" rel="noopener" href="https://github.com/ltyeamin">tong.li</a>
  </p>
</footer>

<script>
  function async(u, c) {
    var d = document, t = 'script',
      o = d.createElement(t),
      s = d.getElementsByTagName(t)[0];
    o.src = u;
    if (c) { o.addEventListener('load', function (e) { c(null, e); }, false); }
    s.parentNode.insertBefore(o, s);
  }
</script>
<script>
  async("https://cdn.staticfile.org/fastclick/1.0.6/fastclick.min.js", function(){
    FastClick.attach(document.body);
  })
</script>

<script>
  var hasLine = 'true';
  async("https://cdn.staticfile.org/highlight.js/9.12.0/highlight.min.js", function(){
    $('figure pre').each(function(i, block) {
      var figure = $(this).parents('figure');
      if (hasLine === 'false') {
        figure.find('.gutter').hide();
      }
      hljs.configure({useBR: true});
      var lang = figure.attr('class').split(' ')[1] || 'code';
      var codeHtml = $(this).html();
      var codeTag = document.createElement('code');
      codeTag.className = lang;
      codeTag.innerHTML = codeHtml;
      $(this).attr('class', '').empty().html(codeTag);
      figure.attr('data-lang', lang.toUpperCase());
      hljs.highlightBlock(block);
    });
  })
</script>
<!-- Baidu Tongji -->



<script src='https://cdn.staticfile.org/mermaid/8.11.2/mermaid.min.js'></script>



<script src="/js/script.js"></script>


  </body>
</html>